package com.hnlwh.utils;

import org.junit.Test;

/**
 * @program: sortingalgorithm
 * @description: 排序算法工具类
 * @author: yuhui
 * @date: 2021-07-28 00:07
 */
public class SortUtils {

    /**
     * @program 冒泡排序
     * @param arrary
     * @return int[]
     */
    public static int[] bubbleSortUtil(int[] arrary){
        for (int i = 0; i < arrary.length-1; i++) {
            boolean sort=true;
            for (int j = 0; j < arrary.length-1-i; j++) {
                if (arrary[j]>arrary[j+1]){
                    int temp = arrary[j+1];
                    arrary[j+1]=arrary[j];
                    arrary[j]=temp;
                    sort=false;
                }
            }
            if (sort==true) break;;
        }
        return arrary;
    }

    /**
     * @program 插入排序
     * @param array
     * @return int[]
     */
    public static int[] insertionSortUtil(int[] array){
        int current;
        for (int i = 0; i < array.length-1; i++) {
            current = array[i+1];
            int preIndex = i;
            while (preIndex >= 0 && current<array[preIndex]){
                array[preIndex+1] = array[preIndex];
                preIndex--;
            }
            array[preIndex+1] = current;
        }
        return array;
    }

    /**
     * @program 选择排序
     * @param array
     * @return
     */

    public static int[] selectionSort(int[] array){

        for (int i = 0; i < array.length; i++) {
            int minIndex=i;

            for (int j = i; j < array.length; j++) { //通过循比较找到最小值索引
                if (array[minIndex]>array[j]){
                    minIndex = j;
                }
            }
            if (i!=minIndex){ // 将最小值与i交换
                int temp=array[minIndex];
                array[minIndex]=array[i];
                array[i]=temp;
            }
        }
        return array;
    }

    @Test
    public void selectionSortTest(){

        int[] array={42,56,23,6,915,123,54,85,2,1,354,6};
        selectionSort(array);

    }

    /**
     *
     * @param array
     * @param low
     * @param mid
     * @param high
     * @param tmp
     */
    private static void merge(int[] array, int low ,int mid,int high,int[] tmp){
        int i = 0;
        int j = low ,k = mid+1;
        while (j <= mid && k <= high){
            if (array[j] < array[k]){
                tmp[i++] = array[j++];
            }
            else{
                tmp[i++] = array[k++];
            }
        }
        while (j<=mid){
            tmp[i++] = array[j++];
        }
        while (k<=high){
            tmp[i++] = array[k++];
        }
        for (int d = 0;d<i;d++){
            array[low+d]=tmp[d];
        }
    }

    /**
     *
     * @param array
     * @param low
     * @param high
     * @param tmp
     *
     * @program 归并排序
     */
    public static void mergeSort(int[] array, int low ,int high,int[] tmp){
        if (low<high){
            int mid=(low+high)/2;
            mergeSort(array,low,mid,tmp);//对左边进行排序
            mergeSort(array,mid+1,high,tmp);//对右边进行排序
            merge(array,low,mid,high,tmp);//合并两个有序序列
        }
    }

    @Test
    public void margeS(){
        int[] array={21,65,3,215,94,86,53,21,531,53,12,5,6,4};

        int[] tem=new int[array.length];
        mergeSort(array,0,array.length-1,tem);

        for ( int a: array
             ) {
            System.out.print(a+" ");
        }
    }

    /**
     * @program 希尔排序
     * @param array
     * @return
     */
    private static int[] shellSort(int[] array){
        int len = array.length;

        for (int gap = (int) Math.floor(len / 2); gap > 0; gap = (int) Math.floor(gap / 2)) { //每次为2n减少循环次数

            for (int i = gap; i < len; i++) {  // 控制列数n/2       插入排序
                int j = i;

                int current = array[i];

                while (j - gap >= 0 && current < array[j - gap]) { //通过插入排序 对gap为一个周期的数组组成列进行排序
                    array[j] = array[j - gap];

                    j  -= gap; // 通过-=gap 进行对同一列的下一行进行比较

                }

                array[j] = current;

            }

        }
        return array;
    }

    @Test
    public void shellSortTest(){
        int[] array={54,53,12,56,98,44,55,66,12,78,77};
        int[] shellSort = shellSort(array);
        for (int shell: shellSort
             ) {
            System.out.print(shell+" ");
        }
    }


}
